@article{FoussPRS07,
  author    = {Fran\c{c}ois Fouss and
               Alain Pirotte and
               Jean-Michel Renders and
               Marco Saerens},
  title     = {Random-Walk Computation of Similarities between Nodes of
               a Graph with Application to Collaborative Recommendation},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {19},
  number    = {3},
  year      = {2007},
  pages     = {355--369}
}

@inproceedings{YenSMS08,
  author    = {Luh Yen and
               Marco Saerens and
               Amin Mantrach and
               Masashi Shimbo},
  title     = {A family of dissimilarity measures between nodes generalizing
               both the shortest-path and the commute-time distances},
  booktitle = {KDD},
  year      = {2008},
  pages     = {785--793}
}


@inproceedings{DongCL08,
  author    = {Wei Dong and
               Moses Charikar and
               Kai Li},
  title     = {Asymmetric distance estimation with sketches for similarity
               search in high-dimensional spaces},
  booktitle = {SIGIR},
  year      = {2008},
  pages     = {123--130}
}

@inproceedings{Broder00,
  author    = {Andrei Z. Broder},
  title     = {Identifying and Filtering Near-Duplicate Documents},
  booktitle = {CPM},
  year      = {2000},
  pages     = {1--10}
}


@article{BroderGMZ97,
  author    = {Andrei Z. Broder and
               Steven C. Glassman and
               Mark S. Manasse and
               Geoffrey Zweig},
  title     = {Syntactic Clustering of the Web},
  journal   = {Computer Networks},
  volume    = {29},
  number    = {8},
  year      = {1997},
  pages     = {1157--1166}
}

@inproceedings{DongWCL08,
  author    = {Wei Dong and
               Zhe Wang and
               Moses Charikar and
               Kai Li},
  title     = {Efficiently matching sets of features with random histograms},
  booktitle = {ACM Multimedia},
  year      = {2008},
  pages     = {179--188}
}


@article{CLRS,
  author    = {Thomas H. Cormen and
  		Charles E. Leiserson and
		Ronald L. Rivest and
		Clifford Stein},
  title     = {Introduction to Algorithms},
  journal   = {MIT Press and McGraw-Hill},
  volume    = {24.3},
  year      = {2001},
  pages	= {595--601}
}

@article{B85,
  author    = {Jean Bourgain},
  title     = {On {L}ipschitz embeddings of finite metric spaces in Hilbert space},
  journal   = {Israel Journal of Mathematics},
  volume    = {52(1-2)},
  year      = {1985},
  pages	= {46--52}
}

@article{M96,
  author    = {Jiri Matousek},
  title     = {On the distortion required for embedding finite metric spaces into normed spaces},
  journal   = {Israel Journal of Mathematics},
  volume    = {93(1)},
  year      = {1996},
  pages	= {333--344}
}

@article{FRT04,
  author    = {Jittat Fakcharoenphol and
               Satish Rao and
               Kunal Talwar},
  title     = {A tight bound on approximating arbitrary metrics by tree
               metrics},
  journal   = {J. Comp. Syst. Sci.},
  volume    = {69},
  number    = {3},
  year      = {2004},
  pages     = {485--497}
}

@article{B08,
  author    = {Surender Baswana},
  title     = {Streaming algorithm for graph spanners - single pass and
               constant processing time per edge},
  journal   = {Inf. Process. Lett.},
  volume    = {106},
  number    = {3},
  year      = {2008},
  pages     = {110--114}
}

@inproceedings{FKMSZ05,
  author    = {Joan Feigenbaum and
               Sampath Kannan and
               Andrew McGregor and
               Siddharth Suri and
               Jian Zhang},
  title     = {Graph distances in the streaming model: the value of space},
  booktitle = {SODA},
  year      = {2005},
  pages     = {745--754}
}

@inproceedings{TZ01,
  author    = {Mikkel Thorup and
               Uri Zwick},
  title     = {Approximate distance oracles},
  booktitle = {STOC},
  year      = {2001},
  pages     = {183--192}
}


@article{TZ05,
  author    = {Mikkel Thorup and
               Uri Zwick},
  title     = {Approximate distance oracles},
  journal   = {J. ACM},
  volume    = {52},
  number    = {1},
  year      = {2005},
  pages     = {1--24}
}

@inproceedings{B96,
  author    = {Yair Bartal},
  title     = {Probabilistic Approximations of Metric Spaces and Its Algorithmic
               Applications},
  booktitle = {FOCS},
  year      = {1996},
  pages     = {184--193}
}

@inproceedings{B98,
  author    = {Yair Bartal},
  title     = {On Approximating Arbitrary Metrices by Tree Metrics},
  booktitle = {STOC},
  year      = {1998},
  pages     = {161--168}
}

@article{GPPR04,
  author    = {Cyril Gavoille and
               David Peleg and
               St{\'e}phane P{\'e}rennes and
               Ran Raz},
  title     = {Distance labeling in graphs},
  journal   = {J. Algorithms},
  volume    = {53},
  number    = {1},
  year      = {2004},
  pages     = {85--112}
}

@article{KKKP04,
  author    = {Michal Katz and
               Nir A. Katz and
               Amos Korman and
               David Peleg},
  title     = {Labeling Schemes for Flow and Connectivity},
  journal   = {SIAM J. Comput.},
  volume    = {34},
  number    = {1},
  year      = {2004},
  pages     = {23--40}
}

@article{CFIKP09,
  author    = {Reuven Cohen and
               Pierre Fraigniaud and
               David Ilcinkas and
               Amos Korman and
               David Peleg},
  title     = {Labeling Schemes for Tree Representation},
  journal   = {Algorithmica},
  volume    = {53},
  number    = {1},
  year      = {2009},
  pages     = {1--15}
}

@inproceedings{N09,
  author    = {Marc Najork},
  title     = {The scalable hyperlink store},
  booktitle = {Hypertext},
  year      = {2009},
  pages     = {89--98}
}



@inproceedings{CHKZ02,
  author    = {Edith Cohen and
               Eran Halperin and
               Haim Kaplan and
               Uri Zwick},
  title     = {Reachability and distance queries via 2-hop labels},
  booktitle = {SODA},
  year      = {2002},
  pages     = {937--946}
}

@inproceedings{G07,
  author    = {Andrew V. Goldberg},
  title     = {Point-to-Point Shortest Path Algorithms with Preprocessing},
  booktitle = {SOFSEM (1)},
  year      = {2007},
  pages     = {88--102}
}

@incollection{DGJ08,
  author    = {Camil Demetrescu and
               Andrew V. Goldberg and
               David S. Johnson},
  title     = {Implementation Challenge for Shortest Paths},
  booktitle = {Encyclopedia of Algorithms},
  year      = {2008}
}

@inproceedings{GKW07,
  author    = {Andrew V. Goldberg and
               Haim Kaplan and
               Renato Fonseca F. Werneck},
  title     = {Better Landmarks Within Reach},
  booktitle = {WEA},
  year      = {2007},
  pages     = {38--51}
}







@article{MoralesGupta09,
  author    = {Rams{\'e}s Morales and
               Indranil Gupta},
  title     = {AVCOL: Availability-aware information aggregation in large
               distributed systems under uncollaborative behavior},
  journal   = {Computer Networks},
  volume    = {53},
  number    = {13},
  year      = {2009},
  pages     = {2360-2372}
}

@article{MoralesGuptaTwo09,
  author    = {Rams{\'e}s Morales and
               Indranil Gupta},
  title     = {AVMON: Optimal and Scalable Discovery of Consistent Availability
               Monitoring Overlays for Distributed Systems},
  journal   = {IEEE Trans. Parallel Distrib. Syst.},
  volume    = {20},
  number    = {4},
  year      = {2009},
  pages     = {446-459}
}

@inproceedings{DasSarmaNPT10,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai and
               Gopal Pandurangan and
               Prasad Tetali},
  title     = {Efficient distributed random walks with applications},
  booktitle = {PODC},
  year      = {2010},
  pages     = {201-210}
}

@inproceedings{NanongkaiDP11,
  author    = {Danupon Nanongkai and
               Atish {Das Sarma} and
               Gopal Pandurangan},
  title     = {A tight unconditional lower bound on distributed randomwalk
               computation},
  booktitle = {PODC},
  year      = {2011},
  pages     = {257-266}
}

@InProceedings{mihail-topaware,
  author = 	 {C. Gkantsidis and G. Goel and M. Mihail and A. Saberi},
  title = 	 {Towards Topology Aware Networks},
  booktitle = 	 {IEEE INFOCOM},
  year = 	 {2007}
}

@article{elkin-survey,
    author = "M. Elkin",
    title = "An Overview of Distributed Approximation",
    journal = {ACM SIGACT News Distributed Computing Column},
    year = {2004},
    month = {December},
    volume = {35},
    number = {4},
    pages = {40--57}
}

@incollection{dubhashi,
author = "D. Dubhashi and F. Grandioni and A. Panconesi",
title  = "Distributed Algorithms via LP Duality and Randomization",
booktitle  =  "Handbook of Approximation Algorithms and Metaheuristics",
year =  2007
}

@article{khan-disc,
 author = {M. Khan and G. Pandurangan},
 title = {A Fast Distributed Approximation Algorithm for Minimum Spanning Trees},
 journal = {Distributed Computing},
 year = {2008},
 volume = {20},
 pages = {391-402}
}

@InProceedings{khan-podc,
author = {M. Khan and  F. Kuhn and D. Malkhi and G. Pandurangan and K. Talwar},
title = {Efficient Distributed Approximation Algorithms via Probabilistic Tree
Embeddings},
booktitle = {Proc. 27th ACM Symp. on Principles of Distributed Computing (PODC)},
year = {2008},
note = {Journal version: {\em Distributed Computing}, 2012}
}

@article{kutten-domset,
    author = "S. Kutten and D. Peleg",
    title = "Fast distributed construction of k-dominating sets and applications",
    journal = {J. Algorithms},
    year = {1998},
    volume = {28},
    pages = {40--66}
}

@article{kempe,
author = {D. Kempe and F. McSherry},
title=  {A Decentralized Algorithm for Spectral Analysis},
 journal = {Journal of
Computer and System Sciences},
volume = {74(1)},
year = {2008},
pages = {70-83}
}


@InProceedings{BFFKRW,
  author = 	 {T. Batu and E. Fischer and L. Fortnow and R. Kumar and R. Rubenfeld and P. White},
  title = 	 {Testing Random Variables for Independence and Identity},
  booktitle = 	 {Proc. of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS)},
  pages = 	 {442--451},
  year = 	 {2001}
}

@Article{JS89,
  author = 	 {M. Jerrum and A. Sinclair},
  title = 	 {Approximating the permanent},
  journal = 	 {SIAM Journal of Computing},
  year = 	 {1989},
  volume = 	 {18},
  number = 	 {6},
  pages = 	 {1149--1178}
}

@misc{LPW,
  title={{Markov chains and mixing times}},
  author={Levin, D.A. and Y.(Yuval) Peres and Elizabeth L.(Elizabeth Lee) Wilmer},
  year={2009},
  publisher={American Mathematical Society}
}

@article{Lyons,
  author    = {Russell Lyons},
  title     = {Asymptotic Enumeration of Spanning Trees},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {14},
  number    = {4},
  year      = {2005},
  pages     = {491-522},
  ee        = {http://dx.doi.org/10.1017/S096354830500684X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Vitter85,
  author    = {Jeffrey Scott Vitter},
  title     = {Random Sampling with a Reservoir},
  journal   = {ACM Trans. Math. Softw.},
  volume    = {11},
  number    = {1},
  year      = {1985},
  pages     = {37-57},
  note      = {Also appeared in FOCS'83},
  ee        = {http://doi.acm.org/10.1145/3147.3165},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS(mihail,
 author =     {C. Gkantsidis and  M. Mihail and A. Saberi},
 title =       {Throughput and Congestion in Power-Law Graphs},
booktitle = {SIGMETRICS},
 pages =       {148-159},
  year =     {2003}
  )

@article(dinwoodie,
author = {I. H. Dinwoodie},
title = {A Probability Inequality for the Occupation Measure of a Reversible Markov Chain},
journal = {The Annals of Applied Probability},
volume = {5(1)},
year =  {1995},
pages = {37-43}
)

@INPROCEEDINGS(elkin,
 author = {Elkin, M.},
 title = {Unconditional Lower Bounds on the Time-Approximation Tradeoffs for the Distributed Minimum Spanning Tree Problem},
 booktitle = {Proceedings of Symposium on Theory of Computing (STOC)},
 year = {2004},
 month = {June},
 CITY = "Chicago",
 COUNTRY = "USA",
)

@inproceedings{DNP09-podc,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai
               and Gopal Pandurangan},
  title     = {Fast Distributed Random Walks},
  booktitle = {PODC},
  year      = {2009}
}

@BOOK(lynch,
 author = {N. Lynch},
 title = {Distributed Algorithms},
 publisher = {Morgan Kaufmann Publishers, San Mateo, CA},
 year = {1996}
)

@inproceedings{peleg-bound,
    author = "D. Peleg and V. Rabinovich",
    title = "A near-tight lower bound on the time complexity of distributed MST construction",
    booktitle = "Proc. of the 40th IEEE Symp. on Foundations of Computer Science",
    pages = "253--261",
    year = "1999"
}

@inproceedings{frieze,
    author = "C. Cooper and A. Frieze and T. Radzik",
    title = "Multiple random walks in random regular graphs",
    booktitle = "Preprint",
    year = "2009"
}


@article{Gillman98,
  author    = {David Gillman},
  title     = {A Chernoff Bound for Random Walks on Expander Graphs},
  journal   = {SIAM J. Comput.},
  volume    = {27},
  number    = {4},
  year      = {1998},
  pages     = {1203-1220},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/26876},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{Jonasson98,
  author    = {Johan Jonasson},
  title     = {On the Cover Time for Random Walks on Random Graphs},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {7},
  number    = {3},
  year      = {1998},
  pages     = {265-279}
}

@inproceedings{Wilson96,
  author    = {David Bruce Wilson},
  title     = {Generating Random Spanning Trees More Quickly than the Cover
               Time},
  booktitle = {STOC},
  year      = {1996},
  pages     = {296-303},
  ee        = {http://doi.acm.org/10.1145/237814.237880}
}


@ARTICLE{JS00,
    author = {Johan Jonasson and Oded Schramm},
    title = {On the cover time of planar graphs},
    journal = {Elec. Comm. Probab},
    year = {2000},
    volume = {5},
    pages = {85-90}
}

@inproceedings{CooperF03,
  author    = {Colin Cooper and
               Alan M. Frieze},
  title     = {The cover time of sparse random graphs},
  booktitle = {SODA},
  year      = {2003},
  pages     = {140-147},
  ee        = {http://doi.acm.org/10.1145/644108.644134}
}


@inproceedings{BroderK88,
  author    = {Andrei Z. Broder and
               Anna R. Karlin},
  title     = {Bounds on the Cover Time (Preliminary Version)},
  booktitle = {FOCS},
  year      = {1988},
  pages     = {479-487}
}


@inproceedings{ChandraRRST89,
  author    = {Ashok K. Chandra and
               Prabhakar Raghavan and
               Walter L. Ruzzo and
               Roman Smolensky and
               Prasoon Tiwari},
  title     = {The Electrical Resistance of a Graph Captures its Commute
               and Cover Times (Detailed Abstract)},
  booktitle = {STOC},
  year      = {1989},
  pages     = {574-586}
}


@article{ST08,
  author    = {Rahul Sami and
               Andy Twigg},
  title     = {Lower bounds for distributed markov chain problems},
  journal   = {CoRR},
  volume    = {abs/0810.5263},
  year      = {2008},
  ee        = {http://arxiv.org/abs/0810.5263}
}

@article{AHLP01,
  author    = {Lada A. Adamic and
               Rajan M. Lukose and
               Amit R. Puniyani and
               Bernardo A. Huberman},
  title     = {Search in Power-Law Networks},
  journal   = {Physical Review},
  volume    = {64},
  year      = {2001},
  ee        = {http://arxiv.org/abs/cs.NI/0103016}
}

@inproceedings{BAS04,
  author    = {Ashwin R. Bharambe and
               Mukesh Agrawal and
               Srinivasan Seshan},
  title     = {Mercury: supporting scalable multi-attribute range queries},
  booktitle = {SIGCOMM},
  year      = {2004},
  pages     = {353-366},
  ee        = {http://doi.acm.org/10.1145/1015467.1015507}
}

@inproceedings{LCCLS02,
  author    = {Qin Lv and
               Pei Cao and
               Edith Cohen and
               Kai Li and
               Scott Shenker},
  title     = {Search and replication in unstructured peer-to-peer networks},
  booktitle = {ICS},
  year      = {2002},
  pages     = {84-95},
  ee        = {http://doi.acm.org/10.1145/514191.514206}
}

@inproceedings{GMS05,
  author    = {Christos Gkantsidis and
               Milena Mihail and
               Amin Saberi},
  title     = {Hybrid search schemes for unstructured peer-to-peer networks},
  booktitle = {INFOCOM},
  year      = {2005},
  pages     = {1526-1537},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2005.1498436}
}

@inproceedings{C05,
  author    = {Brian F. Cooper},
  title     = {Quickly Routing Searches Without Having to Move Content},
  booktitle = {IPTPS},
  year      = {2005},
  pages     = {163-172},
  ee        = {http://dx.doi.org/10.1007/11558989_15}
}


@article{ZS06,
  author    = {Ming Zhong and
               Kai Shen},
  title     = {Random walk based node sampling in self-organizing networks},
  journal   = {Operating Systems Review},
  volume    = {40},
  number    = {3},
  year      = {2006},
  pages     = {49-55},
  ee        = {http://doi.acm.org/10.1145/1151374.1151386}
}

@inproceedings{KKD01,
  author    = {David Kempe and
               Jon M. Kleinberg and
               Alan J. Demers},
  title     = {Spatial gossip and resource location protocols},
  booktitle = {STOC},
  year      = {2001},
  pages     = {163-172},
  ee        = {http://doi.acm.org/10.1145/380752.380796}
}

@inproceedings{K00,
  author    = {Jon M. Kleinberg},
  title     = {The small-world phenomenon: an algorithm perspective},
  booktitle = {STOC},
  year      = {2000},
  pages     = {163-170},
  ee        = {http://doi.acm.org/10.1145/335305.335325}
}

@inproceedings{KR04,
  author    = {David R. Karger and
               Matthias Ruhl},
  title     = {Simple efficient load balancing algorithms for peer-to-peer
               systems},
  booktitle = {SPAA},
  year      = {2004},
  pages     = {36-43},
  ee        = {http://doi.acm.org/10.1145/1007912.1007919}
}

@inproceedings{ZSS05,
  author    = {Ming Zhong and
               Kai Shen and
               Joel I. Seiferas},
  title     = {Non-uniform random membership management in peer-to-peer
               networks},
  booktitle = {INFOCOM},
  year      = {2005},
  pages     = {1151-1161},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2005.1498342}
}

@article{MRRT53,
    abstract = {A general method, suitable for fast computing machines, for investigating such properties as equations of state for substances consisting of interacting individual molecules is described. The method consists of a modified Monte Carlo integration over configuration space. Results for the two-dimensional rigid-sphere system have been obtained on the Los Alamos MANIAC and are presented here. These results are compared to the free volume equation of state and to a four-term virial coefficient expansion.
    The Journal of Chemical Physics is copyrighted by The American Institute of Physics.},
    author = {Metropolis, Nicholas   and Rosenbluth, Arianna  W.  and Rosenbluth, Marshall  N.  and Teller, Augusta  H.  and Teller, Edward  },
    citeulike-article-id = {531300},
    doi = {http://dx.doi.org/10.1063/1.1699114},
    journal = {The Journal of Chemical Physics},
    keywords = {annealing, simulated},
    number = {6},
    pages = {1087--1092},
    posted-at = {2007-07-12 12:49:56},
    priority = {2},
    publisher = {AIP},
    title = {Equation of State Calculations by Fast Computing Machines},
    url = {http://dx.doi.org/10.1063/1.1699114},
    volume = {21},
    year = {1953}
}

@article{Hastings70,
    abstract = {A generalization of the sampling method introduced by Metropolis et al. (1953) is presented along with an exposition of the relevant theory, techniques of application and methods and difficulties of assessing the error in Monte Carlo estimates. Examples of the methods, including the generation of random orthogonal matrices and potential applications of the methods to numerical problems arising in statistics, are discussed. 10.1093/biomet/57.1.97},
    author = {Hastings, W. K. },
    citeulike-article-id = {1015842},
    doi = {http://dx.doi.org/10.1093/biomet/57.1.97},
    journal = {Biometrika},
    keywords = {approximate-methods, bayesian},
    month = {April},
    number = {1},
    pages = {97--109},
    posted-at = {2008-10-31 16:19:43},
    priority = {2},
    title = {Monte Carlo sampling methods using Markov chains and their applications},
    url = {http://dx.doi.org/10.1093/biomet/57.1.97},
    volume = {57},
    year = {1970}
}

@inproceedings{LawS03,
  author    = {Ching Law and
               Kai-Yeung Siu},
  title     = {Distributed Construction of Random Expander Networks},
  booktitle = {INFOCOM},
  year      = {2003},
  ee        = {http://www.ieee-infocom.org/2003/papers/52_02.PDF}
}

@book{chung,
 author = {Fan Chung},
 title = {Spectral Graph Theory},
 year = {1997},
 publisher = {American Mathematical Society},
 address = {Providence, RI, USA}
 }


@book{peleg,
 author = {David Peleg},
 title = {Distributed computing: a locality-sensitive approach},
 year = {2000},
 isbn = {0-89871-464-8},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }


@inproceedings{PK09,
  author    = {Gopal Pandurangan and Maleq Khan},
  title     = {Theory of Communication Networks},
  booktitle = {Algorithms and Theory of Computation Handbook, Second Edition},
  year      = {2009},
  PUBLISHER =    {CRC Press},
}




@inproceedings{AKL+79,
  author    = {Romas Aleliunas and
               Richard M. Karp and
               Richard J. Lipton and
               L{\'a}szl{\'o} Lov{\'a}sz and
               Charles Rackoff},
  title     = {Random Walks, Universal Traversal Sequences, and the Complexity
               of Maze Problems},
  booktitle = {FOCS},
  year      = {1979},
  pages     = {218-223}
}



@article{BFG+03,
 author = {H. Baala and O. Flauzac and J. Gaber and M. Bui and T. El-Ghazawi},
 title = {A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks},
 journal = {J. Parallel Distrib. Comput.},
 volume = {63},
 number = {1},
 year = {2003},
 issn = {0743-7315},
 pages = {97--104},
 doi = {http://dx.doi.org/10.1016/S0743-7315(02)00028-X},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 }

@inproceedings{GoyalRV09,
  author    = {Navin Goyal and
               Luis Rademacher and
               Santosh Vempala},
  title     = {Expanders via random spanning trees},
  booktitle = {SODA},
  year      = {2009},
  pages     = {576-585},
  ee        = {http://doi.acm.org/10.1145/1496770.1496834}
}

@inproceedings{LKRG03,
  author    = {Dmitri Loguinov and
               Anuj Kumar and
               Vivek Rai and
               Sai Ganesh},
  title     = {Graph-theoretic analysis of structured peer-to-peer systems:
               routing distances and fault resilience},
  booktitle = {SIGCOMM},
  year      = {2003},
  pages     = {395-406},
  ee        = {http://doi.acm.org/10.1145/863955.863999}
}



@inproceedings{AAKKLT,
  author    = {Noga Alon and
               Chen Avin and
               Michal Kouck{\'y} and
               Gady Kozma and
               Zvi Lotker and
               Mark R. Tuttle},
  title     = {Many random walks are faster than one},
  booktitle = {SPAA},
  year      = {2008},
  pages     = {119-128},
  ee        = {http://doi.acm.org/10.1145/1378533.1378557}
}


@INPROCEEDINGS(costsens,
author = {B. Awerbuch and A. Baratz and D. Peleg},
 title = {Cost-sensitive analysis of communication protocols},
booktitle =  {  9th ACM PODC},
 pages = {177-187},
 year ={ 1990}
 )

@article{AP92,
 author = {Baruch Awerbuch and David Peleg},
 title = {Routing with polynomial communication-space trade-off},
 journal = {SIAM J. Discret. Math.},
 volume = {5},
 number = {2},
 year = {1992},
 issn = {0895-4801},
 pages = {151--162},
 doi = {http://dx.doi.org/10.1137/0405013},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@inproceedings{AtishGP08,
  author    = {Atish {Das Sarma} and
               Sreenivas Gollapudi and
               Rina Panigrahy},
  title     = {Estimating PageRank on graph streams},
  booktitle = {PODS},
  year      = {2008},
  pages     = {69-78},
  ee        = {http://doi.acm.org/10.1145/1376916.1376928}
}


@book{MU-book-05,
 author = {Michael Mitzenmacher and Eli Upfal},
 title = {Probability and Computing: Randomized Algorithms and Probabilistic Analysis},
 year = {2005},
 isbn = {0521835402},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
 }

@inproceedings{IJ90,
  author    = {Amos Israeli and
               Marc Jalfon},
  title     = {Token Management Schemes and Random Walks Yield Self-Stabilizing
               Mutual Exclusion},
  booktitle = {PODC},
  year      = {1990},
  pages     = {119-131},
  ee        = {http://doi.acm.org/10.1145/93385.93409}
}


@inproceedings{BBF04,
  author    = {Thibault Bernard and
               Alain Bui and
               Olivier Flauzac},
  title     = {Random Distributed Self-stabilizing Structures Maintenance},
  booktitle = {ISSADS},
  year      = {2004},
  pages     = {231-240},
  ee        = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3061{\&}spage=231}
}

@article{CTW93,
 author = {Don Coppersmith and Prasad Tetali and Peter Winkler},
 title = {Collisions among random walks on a graph},
 journal = {SIAM J. Discret. Math.},
 volume = {6},
 number = {3},
 year = {1993},
 issn = {0895-4801},
 pages = {363--374},
 doi = {http://dx.doi.org/10.1137/0406029},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@article{DSW06,
  author    = {Shlomi Dolev and
               Elad Schiller and
               Jennifer L. Welch},
  title     = {Random Walk for Self-Stabilizing Group Communication in
               Ad Hoc Networks},
  journal   = {IEEE Trans. Mob. Comput.},
  volume    = {5},
  number    = {7},
  year      = {2006},
  pages     = {893-905},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/TMC.2006.104},
  note      = {also in PODC'02}
}


@inproceedings{DSW02,
  author    = {Shlomi Dolev and
               Elad Schiller and
               Jennifer L. Welch},
  title     = {Random walk for self-stabilitzing group communication in
               ad hoc networks},
  booktitle = {PODC},
  year      = {2002},
  pages     = {259},
  ee        = {http://doi.acm.org/10.1145/571825.571872}
}


@article{DT07,
  title={{Spanders: Distributed spanning expanders}},
  author={Dolev, S. and Tzachar, N.},
  journal={Dept. of Computer Science, Ben-Gurion University, TR-08-02},
  year={2007}
}


@inproceedings{Broder89,
  author    = {Andrei Z. Broder},
  title     = {Generating Random Spanning Trees},
  booktitle = {FOCS},
  year      = {1989},
  pages     = {442-447}
}


@inproceedings{BIZ89,
 author = {Judit Bar-Ilan and Dror Zernik},
 title = {Random Leaders and Random Spanning Trees},
 booktitle = {Proceedings of the 3rd International Workshop on Distributed Algorithms},
 year = {1989},
 isbn = {3-540-51687-5},
 pages = {1--12},
 publisher = {Springer-Verlag},
 address = {London, UK},
 }

@inproceedings{BBSB04,
  author    = {Marc Bui and
               Thibault Bernard and
               Devan Sohier and
               Alain Bui},
  title     = {Random Walks in Distributed Computing: A Survey},
  booktitle = {IICS},
  year      = {2004},
  pages     = {1-14},
  ee        = {http://dx.doi.org/10.1007/11553762_1}
}

@inproceedings{MG07,
  author    = {Rams{\'e}s Morales and
               Indranil Gupta},
  title     = {AVMON: Optimal and Scalable Discovery of Consistent Availability
               Monitoring Overlays for Distributed Systems},
  booktitle = {ICDCS},
  year      = {2007},
  pages     = {55},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/ICDCS.2007.87}
  }


 @article{GKM03,
 author = {Ayalvadi J. Ganesh and Anne-Marie Kermarrec and Laurent Massouli\'{e}},
 title = {Peer-to-Peer Membership Management for Gossip-Based Protocols},
 journal = {IEEE Trans. Comput.},
 volume = {52},
 number = {2},
 year = {2003},
 issn = {0018-9340},
 pages = {139--149},
 doi = {http://dx.doi.org/10.1109/TC.2003.1176982},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 }

@INPROCEEDINGS{CDG06,
    author = {T.-H. Hubert Chan and Michael Dinitz and Anupam Gupta},
    title = {Spanners with slack},
    booktitle = {Proceedings of the 14th European Symposium on Algorithms},
    year = {2006},
    pages = {196--207}
}

@inproceedings{TZ01r,
 author = {Thorup, Mikkel and Zwick, Uri},
 title = {Compact routing schemes},
 booktitle = {Proceedings of the thirteenth annual ACM Symposium on Parallel Algorithms and Architectures},
 series = {SPAA '01},
 year = {2001},
 isbn = {1-58113-409-6},
 location = {Crete Island, Greece},
 pages = {1--10},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/378580.378581},
 doi = {http://doi.acm.org/10.1145/378580.378581},
 acmid = {378581},
 publisher = {ACM},
 address = {New York, NY, USA},
}

@inproceedings{ABCDGKNS05,
 author = {Abraham, Ittai and Bartal, Yair and Chan, T-H. Hubert and Dhamdhere, Kedar Dhamdhere and Gupta, Anupam and Kleinberg, Jon and Neiman, Ofer and Slivkins, Aleksandrs},
 title = {Metric Embeddings with Relaxed Guarantees},
 booktitle = {Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science},
 series = {FOCS '05},
 year = {2005},
 isbn = {0-7695-2468-0},
 pages = {83--100},
 numpages = {18},
 url = {http://dx.doi.org/10.1109/SFCS.2005.51},
 doi = {http://dx.doi.org/10.1109/SFCS.2005.51},
 acmid = {1097448},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
}

@book{MR95,
 author = {Motwani, Rajeev and Raghavan, Prabhakar},
 title = {Randomized algorithms},
 year = {1995},
 isbn = {0-521-47465-5},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
} 

@inproceedings{WSS05,
 author = {Wong, Bernard and Slivkins, Aleksandrs and Sirer, Emin G\"{u}n},
 title = {Meridian: a lightweight network location service without virtual coordinates},
 booktitle = {Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications},
 series = {SIGCOMM '05},
 year = {2005},
 isbn = {1-59593-009-4},
 location = {Philadelphia, Pennsylvania, USA},
 pages = {85--96},
 numpages = {12},
 url = {http://doi.acm.org/10.1145/1080091.1080103},
 doi = {http://doi.acm.org/10.1145/1080091.1080103},
 acmid = {1080103},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {nearest neighbor, network locality, node selection},
} 

@article{KSW09,
 author = {Kleinberg, Jon and Slivkins, Aleksandrs and Wexler, Tom},
 title = {Triangulation and embedding using small sets of beacons},
 journal = {J. ACM},
 volume = {56},
 issue = {6},
 month = {September},
 year = {2009},
 issn = {0004-5411},
 pages = {32:1--32:37},
 articleno = {32},
 numpages = {37},
 url = {http://doi.acm.org/10.1145/1568318.1568322},
 doi = {http://doi.acm.org/10.1145/1568318.1568322},
 acmid = {1568322},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Distributed algorithms, doubling dimension, embeddings, metric spaces, triangulation},
} 

@inproceedings{Vivaldi,
  title = {Vivaldi: A Decentralized Network Coordinate  System},
  author = {Frank Dabek and Russ Cox and Frans Kaashoek and Robert Morris},
  booktitle = {Proceedings of the {ACM} {SIGCOMM} '04 Conference},
  year = {2004},
  month = {August},
  address = {Portland, Oregon},
}

@inproceedings{S07,
 author = {Slivkins, Aleksandrs},
 title = {Towards fast decentralized construction of locality-aware overlay networks},
 booktitle = {Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing},
 series = {PODC '07},
 year = {2007},
 isbn = {978-1-59593-616-5},
 location = {Portland, Oregon, USA},
 pages = {89--98},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1281100.1281116},
 doi = {http://doi.acm.org/10.1145/1281100.1281116},
 acmid = {1281116},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {distance labeling, grid dimension, growth-constrained metrics, locality-aware networks, multi-cast trees, routing schemes, triangulation},
} 

@inproceedings{S05b,
 author = {Slivkins, Aleksandrs},
 title = {Distance estimation and object location via rings of neighbors},
 booktitle = {Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing},
 series = {PODC '05},
 year = {2005},
 isbn = {1-58113-994-2},
 location = {Las Vegas, NV, USA},
 pages = {41--50},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/1073814.1073823},
 doi = {http://doi.acm.org/10.1145/1073814.1073823},
 acmid = {1073823},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@inproceedings{S05a,
 author = {Slivkins, Aleksandrs},
 title = {Distributed approaches to triangulation and embedding},
 booktitle = {Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms},
 series = {SODA '05},
 year = {2005},
 isbn = {0-89871-585-7},
 location = {Vancouver, British Columbia},
 pages = {640--649},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=1070432.1070522},
 acmid = {1070522},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 
